def is_valid(grid, row, col, m, n, visited):
    # 检查当前位置(row, col)放置哨位是否有效
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上、下、左、右
    for dr, dc in directions:
        r, c = row + dr, col + dc
        # 如果相邻位置在棋盘范围内且未被监视，则无效
        if 0 <= r < m and 0 <= c < n and not visited[r][c]:
            return False
    return True

def backtrack(grid, row, m, n, visited, count):
    # 基本情况：如果所有行都已处理完毕，检查是否所有陈列室都被监视
    if row == m:
        for r in range(m):
            for c in range(n):
                if not visited[r][c]:
                    return False  # 存在未被监视的陈列室，回溯
        # 所有陈列室都被监视，更新最小哨位数和最佳方案
        nonlocal min_count, best_grid
        if count < min_count:
            min_count = count
            best_grid = [row[:] for row in grid]
        return True

    # 尝试在当前行的每个位置放置哨位
    for col in range(n):
        if grid[row][col] == 0 and is_valid(grid, row, col, m, n, visited):
            # 标记当前位置为已监视
            visited[row][col] = True
            # 递归处理下一行
            if backtrack(grid, row + 1, m, n, visited, count + 1):
                return True
            # 回溯：如果下一行无法满足条件，则取消当前位置的监视
            visited[row][col] = False

    # 当前行无法找到满足条件的哨位安排，返回False
    return False

def find_minimum_guards(m, n):
    # 初始化棋盘和访问数组
    grid = [[0] * n for _ in range(m)]
    visited = [[False] * n for _ in range(m)]
    # 初始化最小哨位数和最佳方案
    global min_count, best_grid
    min_count = float('inf')
    best_grid = None

    # 从第一行开始回溯
    backtrack(grid, 0, m, n, visited, 0)

    # 检查是否找到解
    if min_count == float('inf'):
        return "No Solution！"
    else:
        return min_count, best_grid

def main():
    # 读取输入文件
    with open('Input.txt', 'r') as file:
        m, n = map(int, file.readline().strip().split())

    # 计算最佳哨位安排
    result = find_minimum_guards(m, n)

    # 写入输出文件
    with open('output.txt', 'w') as file:
        if result == "No Solution！":
            file.write(result)
        else:
            min_count, best_grid = result
            file.write(f"{min_count}\n")
            for row in best_grid:
                file.write(' '.join(map(str, row)) + '\n')

if __name__ == "__main__":
    main()
    
